package org.aplombh.java.awcing.basic.dp.compressState;

// 旅行商问题

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;

/**
 * 给定一张 n 个点的带权无向图，点从 0∼n−1 标号，求起点 0 到终点 n−1 的最短 Hamilton 路径。
 * <p>
 * Hamilton 路径的定义是从 0 到 n−1 不重不漏地经过每个点恰好一次。
 * <p>
 * 输入格式
 * 第一行输入整数 n。
 * <p>
 * 接下来 n 行每行 n 个整数，其中第 i 行第 j 个整数表示点 i 到 j 的距离（记为 a[i,j]）。
 * <p>
 * 对于任意的 x,y,z，数据保证 a[x,x]=0，a[x,y]=a[y,x] 并且 a[x,y]+a[y,z]≥a[x,z]。
 * <p>
 * 输出格式
 * 输出一个整数，表示最短 Hamilton 路径的长度。
 * <p>
 * 数据范围
 * 1≤n≤20
 * 0≤a[i,j]≤107
 * 输入样例：
 * 5
 * 0 2 4 5 1
 * 2 0 6 5 3
 * 4 6 0 8 3
 * 5 5 8 0 5
 * 1 3 3 5 0
 * 输出样例：  2 5 8 3
 * 18
 */
public class ShortestHamiltonPath_91 {
    public static void main(String[] args) throws IOException {
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(reader.readLine());
        ShortestHamiltonPath shp = new ShortestHamiltonPath(n);
        for (int i = 0; i < n; i++) {
            String s = reader.readLine();
            for (int j = 0; j < n; j++) {
                String[] r = s.split(" ");
                shp.w[i][j] = Integer.parseInt(r[j]);
            }
        }
        System.out.println(shp.solve());
    }
}

/*
0,1,2,3,4

0->1->2->3 18

0->2->1->3 20  x

1.哪些点被用过:
2.目前停在哪个点上:

点的状态 * 停在哪个点
2^20   * 20   ~  2*10^7

// 从k转移过来
f[state][j] = f[state_k][k] + weight[k][j]
state_k 等于state除掉j之后的集合 state_k中包含k

state 表示为一个20位的整数

000...000

0, 1, 4
用位数表示第几位用过
state = 10011

 */
class ShortestHamiltonPath {
    public static final int N = 20;
    public static final int M = 1 << N; // 所有装填  state 每一位表示是否选择该位 大小为2^n,一共n位

    long[][] f = new long[M][N]; // 从第state个状态转移到第i个点的集合中的最小值,中间的过程不管,找到最小值
    long[][] w = new long[N][N]; // 权重
    Pair[][] path = new Pair[M][N];
    int n;

    ShortestHamiltonPath(int n) {
        init();
        this.n = n;
    }

    void init() {
        // 标记所有状态不合法
        for (int i = 0; i < M; i++) {
            Arrays.fill(f[i], 1 << 30);
        }
        f[1][0] = 0;
    }

    long solve() {
        // 所有情况选点情况
        for (int state = 0; state < M; state++) {
            // 转移到i
            for (int i = 0; i < n; i++) {
                // 经过i
                if ((state >> i & 1) == 1) {
                    // 经过j转移到i
                    for (int j = 0; j < n; j++) {
                        // 将第i位置为0,不经过第i位
                        // 判断该情况下第j点是否为1,
                        if ((((state ^ (1 << i)) >> j) & 1) == 1) {
                            if (f[state][i] > f[state - (1 << i)][j] + w[i][j]) {
                                path[state][i] = new Pair(state - (1 << i), j);
                            }
                            f[state][i] = Math.min(f[state][i], f[state ^ (1 << i)][j] + w[i][j]);
                        }
                    }
                }
            }
        }

        ArrayList<Integer> st = new ArrayList<>();
        st.add(n);

        for (int i = (1 << n) - 1; i > 1; ) {
            for (int j = n - 1; j > 0; ) {
                Pair tmp = path[i][j];
                st.add(tmp.r + 1);
                i = tmp.l;
                j = tmp.r;
            }
        }
        for (int i = st.size() - 1; i >= 0; i--) {
            System.out.print(st.get(i) + " ");
        }
        System.out.println();

        // 所有点都选,最有一点到n的情况
        return f[(1 << n) - 1][n - 1];
    }

}

class Pair {
    int l;
    int r;

    public Pair(int l, int r) {
        this.l = l;
        this.r = r;
    }

    public Pair() {
    }

}